//
// Created by francklinson on 2021/10/10 AT 10:21.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>
#include <string>

using namespace std;

class Solution {
public:
    int arrangeCoins(int n) {
        int i = 1;
        while (true) {
            n -= i;
            if (n < 0)
                return i - 1;
            ++i;
        }
        return -1;
    }
};

class Solution2 {
public:
    int arrangeCoins(int n) {
        //二分
        int left = 1, right = n; // 最多n 最少1
        while (left < right) {
            int mid = (right - left + 1) / 2 + left;
            if ((long long) mid * (mid + 1) <= (long long) 2 * n) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

int main() {
    Solution solution;
    cout << solution.arrangeCoins(5) << endl;
    cout << solution.arrangeCoins(8) << endl;
    cout << solution.arrangeCoins(1) << endl;
    cout << solution.arrangeCoins(3) << endl;
    return 0;
}

